package Offer2017;

/**
 * 最小的K个数
 * Created by 雷文康 on 2018/1/1.
 */
public class Test30 {
    public static void main(String[] args) {
        int []array={4,5,1,-6,9,7,3,8};
        getLeastNumbers(array,3);
    }

    //最大堆法，内存很小也适用
    public static void getLeastNumbers(int[] array, int K){
        if (array == null || array.length < K){
            return;
        }
        for (int i = K / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, K - 1);
        }
        for (int i = K; i < array.length; i++) {
            if (array[i] < array[0]) {
                array[0] = array[i];
                adjustHeap(array, 0, K - 1);
            }
        }
        for (int i = 0; i < K; i++) {
            System.out.println(array[i]);
        }
    }

    private static void adjustHeap(int[] array, int index, int end) {
        for (int i = 2 * index + 1; i <= end; i = 2 * i + 1) {
            if (i < end && array[i] < array[i+1]){
                i++;
            }
            if (array[i] < array[index]) {
                break;
            }
            int temp = array[i];
            array[i] = array[index];
            array[index] = temp;
            index = i;
        }
    }

    //partition函数法，需要改变原先数组
    public static void getLeastNumbers2(int[] array, int K){
        if (array == null || array.length < K){
            return;
        }
        int low = 0;
        int high = array.length - 1;
        int pos = partition(array, low, high);
        while (pos != K - 1){
            if (pos < K - 1){
                low = pos + 1;
                pos = partition(array, low, high);
            } else {
                high = pos - 1;
                pos = partition(array, low, high);
            }
        }
        for (int i = 0; i <= pos; i++) {
            System.out.println(array[i]);
        }
    }

    private static int partition(int[] array, int low, int high){
        int val = array[low];
        while (low < high) {
            while (low < high && array[high] >= val) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= val){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = val;
        return low;
    }
}
